#define _CRT_SECURE_NO_WARNINGS 1
#include <cmath>
#include <iostream>
#include <string>
#include <vector>
#include <algorithm>
#include<math.h>
#include<stdlib.h>
#include<stdio.h>
#include<unordered_map>
#include<queue>
#include<stack>

using namespace std;

class Solution {
public:
    int minMutation(string startGene, string endGene, vector<string>& bank) {
        unordered_set<string> vis;
        unordered_set<string> hash(bank.begin(), bank.end());

        string s = "ACGT";
        if (hash.count(endGene) == 0) return -1;
        else if (startGene == endGene) return 0;

        queue<string> qt;
        qt.push(startGene);
        vis.insert(startGene);

        int ret = 0;
        while (qt.size())
        {
            int sz = qt.size();
            ret++;
            while (sz--)
            {
                for (int i = 0; i < 8; i++)
                {
                    string tmp = qt.front();
                    for (int j = 0; j < 4; j++)
                    {
                        tmp[i] = s[j];
                        if (vis.count(tmp) == 0 && hash.count(tmp))
                        {
                            if (tmp == endGene) return ret;
                            vis.insert(tmp);
                            qt.push(tmp);
                        }
                    }
                }
                qt.pop();
            }
        }
        return -1;
    }
};

int main() {
    return 0;
}